home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / misc_lib / priorque.c < prev   
C/C++ Source or Header  |  1995-12-30  |  20KB  |  428 lines
  1. /*****************************************************************************
  2. * PriorQue.c - implement priority queue, using regular binary trees         *
  3. * (that guarantees only average time of NlogN...) and with the following     *
  4. * operations:                                     *
  5. * 1. PQInit(&PQ) - initialize the queue, must be called before usage.         *
  6. * 2. PQEmpty(PQ) - returns TRUE iff PQ is empty.                 *
  7. * 3. PQCompFunc(&CompFunc) - sets (a pointer to) the function that is         *
  8. *    used to compere two items in the queue. the function should get two     *
  9. *    item pointers, and should return >1, 0, <1 as comparison result for     *
  10. *    greater than, equal, or less than respectively.                 *
  11. * 4. PQFirst(&PQ, Delete) - returns the first element of the priority         *
  12. *    queue, and delete it from queue if delete is TRUE.                 *
  13. * 5. PQInsert(&PQ, NewItem) - insert NewItem into the queue             *
  14. *    (NewItem is a pointer to it), using the comparison function CompFunc.   *
  15. * 6. PQDelete(&PQ, OldItem) - Delete old item from the queue             *
  16. *    again using the comparison function CompFunc.                 *
  17. * 7. PQFind(PQ, OldItem)  - Find old item in queue, again using the         *
  18. *    comparison function CompFunc.                         *
  19. * 8. PQNext(PQ, CmpItem, NULL) - returns the smallest item which is bigger   *
  20. *    than given item CmpItem. PQ is not modified. Return NULL if none.         *
  21. * 9. PQPrint(PQ, &PrintFunc) - print the queue in order using the given      *
  22. *    printing function PrintFunc.                         *
  23. *10. PQFree(&PQ, FreeItems) - Free the queue. The items are also freed if    *
  24. *    FreeItems is TRUE.                                 *
  25. *                                         *
  26. *             Written by Gershon Elber,   Dec 88                   *
  27. *****************************************************************************/
  28.  
  29. #include <stdio.h>
  30. #include <string.h>
  31. #include "irit_sm.h"
  32. #include "priorque.h"
  33. #include "imalloc.h"
  34.  
  35. #define PQ_NEW_NODE(PQ)  { \
  36.     PQ = (PriorQue *) IritMalloc(sizeof(PriorQue)); \
  37.     (PQ) -> Right = (PQ) -> Left = NULL; \
  38.     (PQ) -> Data = NULL; }
  39. #define PQ_FREE_NODE(PQ) { IritFree((VoidPtr) (PQ)); PQ = NULL; }
  40.  
  41. static PQCompFuncType CompFunc = (PQCompFuncType) strcmp;
  42.  
  43. /*****************************************************************************
  44. * DESCRIPTION:                                                               M
  45. * Initializes the priority queue.                         M
  46. *                                                                            *
  47. * PARAMETERS:                                                                M
  48. *   PQ:       To initialize.                                                 M
  49. *                                                                            *
  50. * RETURN VALUE:                                                              M
  51. *   void                                                                     M
  52. *                                                                            *
  53. * KEYWORDS:                                                                  M
  54. *   PQInit, priority queue                                                   M
  55. *****************************************************************************/
  56. void PQInit(PriorQue **PQ)
  57. {
  58.     *PQ = NULL;
  59. }
  60.  
  61. /*****************************************************************************
  62. * DESCRIPTION:                                                               M
  63. * returns TRUE iff PQ priority queue is empty.                     M
  64. *                                                                            M
  65. *                                                                            *
  66. * PARAMETERS:                                                                M
  67. *   PQ:       Priority queue to test for containment.                        M
  68. *                                                                            *
  69. * RETURN VALUE:                                                              M
  70. *   int:      TRUE if not empty, FALSE otherwise.                            M
  71. *                                                                            *
  72. * KEYWORDS:                                                                  M
  73. *   PQEmpty, priority queue                                                  M
  74. *****************************************************************************/
  75. int PQEmpty(PriorQue *PQ)
  76. {
  77.     return PQ == NULL;
  78. }
  79.  
  80. /*****************************************************************************
  81. * DESCRIPTION:                                                               M
  82. * Sets (a pointer to) the function that is used in comparing two items in    M
  83. * the queue.                                                                 M
  84. *    This comparison function will get two item pointers, and should return  M
  85. * >0, 0, <0 as comparison result for greater than, equal, or less than       M
  86. * relation, respectively.                                 M
  87. *                                                                            *
  88. * PARAMETERS:                                                                M
  89. *   NewCompFunc:   A comparison function to used on item in the queue.         M
  90. *                                                                            *
  91. * RETURN VALUE:                                                              M
  92. *   void                                                                     M
  93. *                                                                            *
  94. * KEYWORDS:                                                                  M
  95. *   PQCompFunc, priority queue                                               M
  96. *****************************************************************************/
  97. void PQCompFunc(PQCompFuncType NewCompFunc)
  98. {
  99.     CompFunc = NewCompFunc;
  100. }
  101.  
  102. /*****************************************************************************
  103. * DESCRIPTION:                                                               M
  104. * Returns the first element in the given priority queue, and delete it from  M
  105. * the queue if Delete is TRUE. returns NULL if empty queue.             M
  106. *                                                                            *
  107. * PARAMETERS:                                                                M
  108. *   PQ:        To examine/remove first element from.                         M
  109. *   Delete:    If TRUE first element is being removed from the queue.        M
  110. *                                                                            *
  111. * RETURN VALUE:                                                              M
  112. *   VoidPtr:   A pointer to the first element in the queue.                  M
  113. *                                                                            *
  114. * KEYWORDS:                                                                  M
  115. *   PQFirst, priority queue                                                  M
  116. *****************************************************************************/
  117. VoidPtr PQFirst(PriorQue **PQ, int Delete)
  118. {
  119.     VoidPtr Data;
  120.     PriorQue *Ptemp = (*PQ);
  121.  
  122.     if (*PQ == NULL)
  123.     return NULL;
  124.  
  125.     while (Ptemp -> Right != NULL)
  126.     Ptemp = Ptemp -> Right;                  /* Find smallest item. */
  127.     Data = Ptemp -> Data;
  128.  
  129.     if (Delete)
  130.     PQDelete(PQ, Data);
  131.  
  132.     return Data;
  133. }
  134.  
  135. /*****************************************************************************
  136. * DESCRIPTION:                                                               M
  137. * Insert a new element into the queue (NewItem is a pointer to new element)  M
  138. * using given compare function CompFunc (See PQCompFunc).             M
  139. *   Insert elelemnt will always be a leaf of the constructed tree.         M
  140. *   Returns a pointer to old element if was replaced or NULL if the element  M
  141. * is new.                                                                    M
  142. *                                                                            *
  143. * PARAMETERS:                                                                M
  144. *   PQ:        To insert a new element to.                                   M
  145. *   NewItem:   The new element to insert.                                    M
  146. *                                                                            *
  147. * RETURN VALUE:                                                              M
  148. *   VoidPtr:   An old element NewItem replaced, or NULL otherwise.           M
  149. *                                                                            *
  150. * KEYWORDS:                                                                  M
  151. *   PQInsert, priority queue                                                 M
  152. *****************************************************************************/
  153. VoidPtr PQInsert(PriorQue **PQ, VoidPtr NewItem)
  154. {
  155.     int Compare;
  156.     VoidPtr Data;
  157.  
  158.     if ((*PQ) == NULL) {
  159.     PQ_NEW_NODE(*PQ);
  160.     (*PQ) -> Data = NewItem;
  161.     return NULL;
  162.     }
  163.     else {
  164.     Compare = (*CompFunc)(NewItem, (*PQ) -> Data);
  165.     Compare = SIGN(Compare);
  166.     switch (Compare) {
  167.         case -1:
  168.         return PQInsert(&((*PQ) -> Right), NewItem);
  169.         case 0:
  170.         Data = (*PQ) -> Data;
  171.         (*PQ) -> Data = NewItem;
  172.         return Data;
  173.         case 1:
  174.         return PQInsert(&((*PQ) -> Left), NewItem);
  175.     }
  176.     }
  177.     return NULL;                    /* Makes warning silent. */
  178. }
  179.  
  180. /*****************************************************************************
  181. * DESCRIPTION:                                                               M
  182. * Deletes an old item from the queue, using comparison function CompFunc.    M
  183. *   Returns a pointer to Deleted item if was fould and deleted from the      M
  184. * queure, NULL otherwise.                             M
  185. *                                                                            *
  186. * PARAMETERS:                                                                M
  187. *   PQ:        To delete OldItem from.                                       M
  188. *   OldItem:   Old element in priority queue PQ to remove from.              M
  189. *                                                                            *
  190. * RETURN VALUE:                                                              M
  191. *   VoidPtr:   Removed OldItem if found, NULL otherwise.                     M
  192. *                                                                            *
  193. * KEYWORDS:                                                                  M
  194. *   PQDelete, priority queue                                                 M
  195. *****************************************************************************/
  196. VoidPtr PQDelete(PriorQue **PQ, VoidPtr OldItem)
  197. {
  198.     int Compare;
  199.     PriorQue *Ptemp;
  200.     VoidPtr Data;
  201.     VoidPtr OldData;
  202.  
  203.     if ((*PQ) == NULL) {
  204.     return NULL;
  205.     }
  206.     else {
  207.     Compare = (*CompFunc)(OldItem, (*PQ) -> Data);
  208.     Compare = SIGN(Compare);
  209.     switch (Compare) {
  210.         case -1:
  211.         return PQDelete(&((*PQ) -> Right), OldItem);
  212.         case 0:
  213.         OldData = (*PQ) -> Data;       /* The returned deleted item. */
  214.  
  215.         if ((*PQ) -> Right == NULL && (*PQ) -> Left == NULL) {
  216.             /* Thats easy - we delete a leaf: */
  217.             Data = (*PQ) -> Data;
  218.             PQ_FREE_NODE(*PQ); /* Note *PQ is also set to NULL here. */
  219.         }
  220.         else if ((*PQ) -> Right != NULL) {
  221.             /* replace this node by the biggest in the Right branch: */
  222.             /* move once to the Right and then Left all the time...  */
  223.             Ptemp = (*PQ) -> Right;
  224.             if (Ptemp -> Left != NULL) {
  225.             while (Ptemp -> Left -> Left != NULL)
  226.                 Ptemp = Ptemp -> Left;
  227.             Data = Ptemp -> Left -> Data;/*Save the data pointer.*/
  228.             PQDelete(&(Ptemp -> Left), Data);  /* Delete recurs. */
  229.             (*PQ) -> Data = Data; /* And put that data instead...*/
  230.             }
  231.             else {
  232.             Data = Ptemp -> Data;      /* Save the data pointer. */
  233.             PQDelete(&((*PQ) -> Right), Data); /* Delete recurs. */
  234.             (*PQ) -> Data = Data; /* And put that data instead...*/
  235.             }
  236.         }
  237.         else {                        /* Left != NULL. */
  238.             /* replace this node by the biggest in the Left branch:  */
  239.             /* move once to the Left and then Right all the time...  */
  240.             Ptemp = (*PQ) -> Left;
  241.             if (Ptemp -> Right != NULL)    {
  242.             while (Ptemp -> Right -> Right != NULL)
  243.                 Ptemp = Ptemp -> Right;
  244.             Data = Ptemp -> Right -> Data; /* Save data pointer. */
  245.             PQDelete(&(Ptemp -> Right), Data);  /*Delete recurs. */
  246.             (*PQ) -> Data = Data; /* And put that data instead...*/
  247.             }
  248.             else {
  249.             Data = Ptemp -> Data;      /* Save the data pointer. */
  250.             PQDelete(&((*PQ) -> Left), Data);  /* Delete recurs. */
  251.             (*PQ) -> Data = Data; /* And put that data instead...*/
  252.             }
  253.         }
  254.         return OldData;
  255.         case 1:
  256.         return PQDelete(&((*PQ) -> Left), OldItem);
  257.     }
  258.     }
  259.     return NULL;                    /* Makes warning silent. */
  260. }
  261.  
  262. /*****************************************************************************
  263. * DESCRIPTION:                                                               M
  264. * Finds old item on the queue, PQ, using the comparison    function CompFunc.   M
  265. *   Returns a pointer to item if was fould, NULL otherwise.             M
  266. *                                                                            *
  267. * PARAMETERS:                                                                M
  268. *   PQ:        To search for OldItem at.                                     M
  269. *   OldItem:   Element to search in PQ.                                      M
  270. *                                                                            *
  271. * RETURN VALUE:                                                              M
  272. *   VoidPtr:   Found element or othewise NULL.                               M
  273. *                                                                            *
  274. * KEYWORDS:                                                                  M
  275. *   PQFind, priority queue                                                   M
  276. *****************************************************************************/
  277. VoidPtr PQFind(PriorQue *PQ, VoidPtr OldItem)
  278. {
  279.     int Compare;
  280.  
  281.     if (PQ == NULL) {
  282.     return NULL;
  283.     }
  284.     else {
  285.     Compare = (*CompFunc)(OldItem, PQ -> Data);
  286.     Compare = SIGN(Compare);
  287.     switch (Compare) {
  288.         case -1:
  289.         return PQFind(PQ -> Right, OldItem);
  290.         case 0:
  291.         return PQ -> Data;
  292.         case 1:
  293.         return PQFind(PQ -> Left, OldItem);
  294.     }
  295.     }
  296.     return NULL;                    /* Makes warning silent. */
  297. }
  298.  
  299. /*****************************************************************************
  300. * DESCRIPTION:                                                               M
  301. * Returns the smallest element in PQ that is larger than given element       M
  302. * CmpItem.                                                                   M
  303. *   PQ is not modified. Return NULL if none was found.                 M
  304. *   LargerThan will allways hold the smallest Item Larger than current one.  M
  305. *                                                                            *
  306. * PARAMETERS:                                                                M
  307. *   PQ:           To examine.                                                M
  308. *   CmpItem:      To find the smallest item in PQ that is larger than it.    M
  309. *   LargerThan:   The item that is found larger so far.                      M
  310. *                                                                            *
  311. * RETURN VALUE:                                                              M
  312. *   VoidPtr:     The samllest item in PQ that is larger than CmpItem or      M
  313. *                NULL if no found.                         M
  314. *                                                                            *
  315. * KEYWORDS:                                                                  M
  316. *   PQNext, priority queue                                                   M
  317. *****************************************************************************/
  318. VoidPtr PQNext(PriorQue *PQ, VoidPtr CmpItem, VoidPtr LargerThan)
  319. {
  320.     int Compare;
  321.     PriorQue *Ptemp;
  322.  
  323.     if (PQ == NULL)
  324.     return LargerThan;
  325.     else {
  326.     Compare = (*CompFunc)(CmpItem, PQ -> Data);
  327.     Compare = SIGN(Compare);
  328.     switch (Compare) {
  329.         case -1:
  330.         return PQNext(PQ -> Right, CmpItem, PQ -> Data);
  331.         case 0:
  332.         /* Found it - if its right tree is not empty, returns its    */
  333.         /* smallest, else returns LargerThan...                 */
  334.         if (PQ -> Left != NULL) {
  335.             Ptemp = PQ -> Left;
  336.             while (Ptemp -> Right != NULL) Ptemp = Ptemp -> Right;
  337.             return Ptemp -> Data;
  338.         }
  339.         else
  340.             return LargerThan;
  341.         case 1:
  342.         return PQNext(PQ -> Left, CmpItem, LargerThan);
  343.     }
  344.     }
  345.     return NULL;                    /* Makes warning silent. */
  346. }
  347.  
  348. /*****************************************************************************
  349. * DESCRIPTION:                                                               M
  350. * Scans the priority queue in order and invokes the "printing" routine,      M
  351. * PrintFunc on every item in the queue as its only argument.             M
  352. *                                                                            *
  353. * PARAMETERS:                                                                M
  354. *   PQ:         Pritority queue to traverse.                                 M
  355. *   PrintFunc:  "Printing function".                                         M
  356. *                                                                            *
  357. * RETURN VALUE:                                                              M
  358. *   void                                                                     M
  359. *                                                                            *
  360. * KEYWORDS:                                                                  M
  361. *   PQPrint, priority queue                                                  M
  362. *****************************************************************************/
  363. void PQPrint(PriorQue *PQ, void (*PrintFunc)(VoidPtr))
  364. {
  365.     if (PQ == NULL)
  366.     return;
  367.  
  368.     PQPrint(PQ -> Right, PrintFunc);
  369.  
  370.     (*PrintFunc)(PQ -> Data);
  371.  
  372.     PQPrint(PQ -> Left, PrintFunc);
  373. }
  374.  
  375. /*****************************************************************************
  376. * DESCRIPTION:                                                               M
  377. * Frees the given queue. The elelents are also freed if FreeItems is TRUE.   M
  378. *                                                                            *
  379. * PARAMETERS:                                                                M
  380. *   PQ:         Priority queue to release.                                   M
  381. *   FreeItem:   If TRUE, elements are being freed as well.                   M
  382. *                                                                            *
  383. * RETURN VALUE:                                                              M
  384. *   void                                                                     M
  385. *                                                                            *
  386. * KEYWORDS:                                                                  M
  387. *   PQFree, priority queue                                                   M
  388. *****************************************************************************/
  389. void PQFree(PriorQue *PQ, int FreeItem)
  390. {
  391.     if (PQ == NULL)
  392.     return;
  393.  
  394.     PQFree(PQ -> Right, FreeItem);
  395.     PQFree(PQ -> Left, FreeItem);
  396.  
  397.     if (FreeItem)
  398.     IritFree((char *) PQ -> Data);
  399.     IritFree((char *) PQ);
  400. }
  401.  
  402. /*****************************************************************************
  403. * DESCRIPTION:                                                               M
  404. * Frees the given queue. The elelents are also freed by invoking FreeFunc    M
  405. * onall of them as FreeFunc's only argument.                                 M
  406. *                                                                            *
  407. * PARAMETERS:                                                                M
  408. *   PQ:         Priority queue to release.                                   M
  409. *   FreeFunc:   "Printing function".                                         M
  410. *                                                                            *
  411. * RETURN VALUE:                                                              M
  412. *   void                                                                     M
  413. *                                                                            *
  414. * KEYWORDS:                                                                  M
  415. *   PQFreeFunc, priority queue                                               M
  416. *****************************************************************************/
  417. void PQFreeFunc(PriorQue *PQ, void (*FreeFunc)(VoidPtr))
  418. {
  419.     if (PQ == NULL)
  420.     return;
  421.  
  422.     PQFreeFunc(PQ -> Right, FreeFunc);
  423.     PQFreeFunc(PQ -> Left, FreeFunc);
  424.  
  425.     (FreeFunc)(PQ -> Data);
  426.     IritFree((char *) PQ);
  427. }
  428.